#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
class Solution
{
public:
    // 递归方法：步骤: 1. 访问左子树 2. 访问右子树 3. 返回左右子树的最大深度+1
    int maxDepth(TreeNode *root)
    {
        if (!root)
            return 0;
        return max(maxDepth(root->left), maxDepth(root->right)) + 1;
    }
    // 深度优先遍历方法：步骤: 1. 使用栈模拟递归过程 2. 记录当前节点的深度 3. 更新最大深度
    int maxDepthDFS(TreeNode *root)
    {
        if (!root)
            return 0;
        stack<pair<TreeNode *, int>> st; // 栈中存储节点和当前深度
        st.push({root, 1});              // 根节点入栈，深度为1
        int max_depth = 0;               // 记录最大深度
        while (!st.empty())              // 栈不为空时循环, 访问栈顶节点
        {
            auto [node, depth] = st.top(); // 获取栈顶节点和当前深度
            st.pop();
            if (node) // 节点不为空, 继续访问子节点
            {
                max_depth = max(max_depth, depth); // 更新最大深度
                st.push({node->left, depth + 1});  // 左子节点入栈，深度+1
                st.push({node->right, depth + 1}); // 右子节点入栈，深度+1
            }
        }
        return max_depth;
    }
    // 广度优先遍历方法：步骤: 1. 使用队列进行层次遍历 2. 每访问一层，深度加1
    int maxDepthBFS(TreeNode *root)
    {
        if (!root)
            return 0;
        queue<TreeNode *> q; // 队列用于层次遍历
        q.push(root);        // 根节点入队
        int depth = 0;       // 记录深度
        while (!q.empty())   // 队列不为空时循环
        {
            int size = q.size();           // 当前层的节点数
            depth++;                       // 深度加1
            for (int i = 0; i < size; i++) // 遍历当前层的所有节点
            {
                TreeNode *node = q.front();
                q.pop();
                if (node->left)
                    q.push(node->left); // 左子节点入队
                if (node->right)
                    q.push(node->right); // 右子节点入队
            }
        }
        return depth;
    }
};